package heap;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;



/**
 * 贪心堆
 * 可参考 767题
 * 贪心 ： 先两两轮换排  剩下一直拿能拿的两个轮换  先用大的是因为 个数多的用了之后剩下的就少了  可以和少的轮流排
 *
 * 计数排序法 ：
 */
public class 距离相等的条形码_1054{
            public int[] rearrangeBarcodes(int[] barcodes) {
                int[] res = new int[barcodes.length];
                Queue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
                Map<Integer, Integer> map = new HashMap<>();
                for(int i : barcodes) {
                    Integer cnt = map.get(i);
                    if(cnt == null) {
                        map.put(i, 1);
                    } else{
                        map.put(i, cnt + 1);
                    }
                }
                for(int i : map.keySet()) {
                    pq.offer(new int[]{i, map.get(i)});
                }
                // 两个两个往里边放  不用isEmpty()
                int i = 0;
                while(pq.size() > 1) {
                    int[] a = pq.poll();
                    int[] b = pq.poll();
                    res[i++] = a[0];
                    res[i++] = b[0];
                    if(a[1] >= 2) {
                      pq.offer(new int[]{a[0], a[1] - 1})  ;
                    }
                     if(b[1] >= 2) {
                      pq.offer(new int[]{b[0], b[1] - 1})  ;
                    }
                }
                if(pq.size() == 1) {
                    res[i++] = pq.poll()[0];
                }
                return res;
            }
        }
